package com.suzhenyu.sort;

/**
 * 插入排序
 * @author suzy2
 */
public class InsertSort implements Sort {
    /**
     *    数列前面部分看为有序，
     *    依次将后面的无序数列元素插入到前面的有序数列中，
     *    初始状态有序数列仅有一个元素，即首元素。
     *    在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，
     *    相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。
     * @param ints
     */
    @Override
    public void sort(int[] ints) {
            for(int i=1;i<ints.length;i++){
                // 初始状态有序数列仅有一个元素，即首元素。
                   // 在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列
                    /*
                     * 分为1,2两部分处理，可以囊括j = beg - 1时的情况
                     * 即需要将arr[i]插入到首元素前的位置，若使用一个for
                     * 包括这两部分，则会在发生这种情况时退出
                     */
                    /*1*/
                    int j = i - 1;
                    for ( ; j >= 0; --j) {
                        if (ints[j] <= ints[i]) {
                            break;
                        }
                    }
                    /*2*/
                    if (j != i - 1)
                    {
                        int temp = ints[i];
                        for (int k = i; k > j + 1; --k)
                        {
                            ints[k] = ints[k - 1];
                        }
                        ints[j + 1] = temp;
                    }

            }
    }
}
